package com.chenxys.algorithm.newbie;

import java.util.ArrayList;
import java.util.List;

/**
 * <p>
 *      链表反转：将链表原来为头的节点变成尾 双向链表
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.newbie
 * @date 12/27/23 11:13 PM
 * @Copyright ©
 */
@SuppressWarnings("all")
public class ReverseDoubleList {
    /**
     * <p>
     *     双链表结构
     * </p>
     */
    public static class DoubleNode{
        // 当前节点的值
        public int value;
        // 当前节点指向的上一个节点
        DoubleNode last;
        // 当前节点指向的下一个节点
        DoubleNode next;

        public DoubleNode(int value) {
            this.value = value;
        }
    }

    /**
     * <p>
     *     反转双向链表
     * </p>
     * @param head 待反转双向链表
     * @return 反转后的双向链表
     */
    public static DoubleNode reverseDoubleList(DoubleNode head){
        DoubleNode pre = null;
        DoubleNode next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }
        return pre;
    }


    /**
     * <p>
     *     测试双向链表反转方法是否正确
     * </p>
     * @param head 待反转双向链表
     * @return 反转后的双向链表
     */
    public static DoubleNode testReverseDoubleList(DoubleNode head){
        if (head == null) return  null;
        ArrayList<DoubleNode> list = new ArrayList<>();
        while (head != null){
            list.add(head);
            head = head.next;
        }
        list.get(0).next = null;
        DoubleNode pre = list.get(0);
        int N = list.size();
        for (int i = 0; i < N; i++) {
            DoubleNode cur = list.get(i);
            cur.last = null;
            cur.next = pre;
            pre.last = cur;
            pre = cur;
        }
        return list.get(N - 1);
    }


    /**
     * <p>
     *     生成随机双向链表
     * </p>
     * @param len 链表长度
     * @param value 链表最大值
     * @return 随机双向链表
     */
    public static DoubleNode generateRandomDoubleList(int len, int value) {
        int size = (int) (Math.random() * (len + 1));
        if (size == 0) return null;

        size--;
        DoubleNode head = new DoubleNode((int) (Math.random() * (value + 1)));
        DoubleNode pre = head;
        while (size != 0){
            DoubleNode cur = new DoubleNode((int) (Math.random() * (value + 1)));
            pre.next = cur;
            cur.last = pre;
            pre = cur;
            size--;
        }
        return head;
    }

    
    /**
     * <p>
     *     获取双向链表原有顺序
     * </p>
     * @param head 双向链表
     * @return 记录元素顺序
     */
    public static List<Integer> getDoubleListOriginOrder(DoubleNode head) {
        List<Integer> ans = new ArrayList<>();
        while (head != null) {
            ans.add(head.value);
            head = head.next;
        }
        return ans;
    }

    /**
     * <p>
     *     检查双向链表反转后的顺序是否与原记录相反
     * </p>
     * @param origin 原记录
     * @param head 反转后链表
     * @return 是否相反
     */
    public static boolean checkDoubleListReverse(List<Integer> origin, DoubleNode head) {
        DoubleNode end = null;
        // 先从前至后
        for (int i = origin.size() - 1; i >= 0; i--) {
            if (!origin.get(i).equals(head.value)) return false;
            end = head;
            head = head.next;
        }
        // 再从后到前
        for (int i = 0; i < origin.size(); i++) {
            if (!origin.get(i).equals(end.value)) return false;
            end = end.last;
        }
        return true;
    }

    public static void main(String[] args) {
        int len = 50;
        int value = 100;
        int testTimes = 100000;
        System.out.println("Test Begin!");
        for (int i = 0; i < testTimes; i++) {
            DoubleNode node1 = generateRandomDoubleList(len, value);
            List<Integer> list3 = getDoubleListOriginOrder(node1);
            node1 = reverseDoubleList(node1);
            if (!checkDoubleListReverse(list3, node1)) {
                System.out.println("Oops3!");
            }

            DoubleNode node2 = generateRandomDoubleList(len, value);
            List<Integer> list4 = getDoubleListOriginOrder(node2);
            node2 = reverseDoubleList(node2);
            if (!checkDoubleListReverse(list4, node2)) {
                System.out.println("Oops4!");
            }
        }
        System.out.println("Test Finish!");
    }
}
